package first.niuke.huawei.simple;

/**
 * @ClassName HJ50
 * @description:
 * @author: 荣燊
 * @create: 2021-07-04 10:05
 **/
import java.util.*;

// 四则运算，保证字符串中的有效字符包括[‘0’-‘9’],‘+’,‘-’, ‘*’,‘/’ ,‘(’， ‘)’,‘[’, ‘]’,‘{’ ,‘}’。且表达式一定合法。
public class HJ50 {

    public static void main(String[] args) {
        String s = "(7+5*4*(-3+6))"; // 转化为后缀表达式：[7, 5, 4, *, 3, _, 6, +, *, +],负号在数字的后面

        // 保存后缀表达式的计算值
        Stack<Integer> result = new Stack<>();
        // 字符串 转化为 后缀表达式
        List<String> postfix = toPostfix(s);

        System.out.println("转化为后缀表达式："+postfix);

        for (String e : postfix) {
            if (e.equals("_")) { // 负数标记
                int temp = -result.pop();
                result.push(temp);
            } else if (e.equals("+") || e.equals("-") || e.equals("*") || e.equals("/")) {
                int b = result.pop();
                int a = result.pop();
                if (e.equals("+")) {
                    result.push(a + b);
                } else if (e.equals("-")) {
                    result.push(a - b);
                } else if (e.equals("*")) {
                    result.push(a * b);
                } else {
                    result.push(a / b);
                }
            } else {
                result.push(Integer.parseInt(e));
            }
        }
        System.out.println(result.pop());

    }

    // 字符串 转化为 后缀表达式。有(){}[],多位数，正负数
    private static List<String> toPostfix(String exp) {
        // 保存后缀表达式
        List<String> postfix = new ArrayList<>();
        // 保存操作符
        Stack<String> stack = new Stack<>();

        for (int i = 0; i < exp.length(); ++i) {
            if (exp.charAt(i) == '+') {
                if (stack.isEmpty()) {
                    stack.push(String.valueOf(exp.charAt(i)));
                } else {
                    // 栈不为空，加减符号优先级最低，只能一直出栈
                    while (!stack.isEmpty() && (stack.peek().equals("_") || stack.peek().equals("*") || stack.peek().equals("/") || stack.peek().equals("+") || stack.peek().equals("-"))) {
                        postfix.add(stack.pop());
                    }
                    // 将当前元素加入栈中
                    stack.push(String.valueOf(exp.charAt(i)));
                }
            }

            else if (exp.charAt(i) == '-') {
                if (i == 0) { // 如果是第一个字符，那么这就是负数，用下划线标记
                    stack.push("_");
                } else {
                    // ( { [ 这三个符号之后出现的符号，也表示这个数是负数
                    if (exp.charAt(i - 1) == '(' || exp.charAt(i - 1) == '[' || exp.charAt(i - 1) == '{') {
                        stack.push("_");
                    } else {
                        if (stack.isEmpty()) {
                            stack.push("-");
                        } else {
                            // 栈不为空，加减符号优先级最低，只能一直出栈
                            while (!stack.isEmpty() && (stack.peek().equals("_") || stack.peek().equals("*") || stack.peek().equals("/") || stack.peek().equals("+") || stack.peek().equals("-"))) {
                                postfix.add(stack.pop());
                            }
                            stack.push("-");
                        }
                    }
                }
            }
            //
            else if (exp.charAt(i) == '*' || exp.charAt(i) == '/') {
                if (stack.isEmpty()) {
                    stack.push(String.valueOf(exp.charAt(i)));
                } else {
                    // 栈不为空，那么乘除符号只有遇到 比其优先级小的 才会停止出栈
                    while (!stack.isEmpty() && (stack.peek().equals("_") || stack.peek().equals("*") || stack.peek().equals("/"))) {
                        postfix.add(stack.pop());
                    }
                    stack.push(String.valueOf(exp.charAt(i)));
                }
            }
            // 左括号直接加入到栈中
            else if (exp.charAt(i) == '(' || exp.charAt(i) == '[' || exp.charAt(i) == '{') {
                stack.push(String.valueOf(exp.charAt(i)));
            }
            // 如果是右括号，那就一直出栈，直到和左括号匹配
            else if (exp.charAt(i) == ')') {
                while (!stack.isEmpty() && !stack.peek().equals("(")) {
                    postfix.add(stack.pop());
                }
                stack.pop();
            } else if (exp.charAt(i) == ']') {
                while (!stack.isEmpty() && !stack.peek().equals("[")) {
                    postfix.add(stack.pop());
                }
                stack.pop();
            } else if (exp.charAt(i) == '}') {
                while (!stack.isEmpty() && !stack.peek().equals("{")) {
                    postfix.add(stack.pop());
                }
                stack.pop();
            }
            // 数字
            else {
                // 如果是数字，则将其加入后缀集合中（这里考虑了多位数情况）
                StringBuilder num = new StringBuilder();
                while (i < exp.length() && (exp.charAt(i) >= '0' && exp.charAt(i) <= '9')) {
                    num.append(exp.charAt(i));
                    ++i;
                }
                --i;
                postfix.add(num.toString());
            }
        }

        // 将栈中所有元素出栈，添加到后缀表达式中
        while (!stack.isEmpty()) {
            postfix.add(stack.pop());
        }

        return postfix;
    }
}
